package datastructure.binarytree;

import java.util.Stack;

/**
 * Created by hao on 17-3-14.
 */

class BinaryTreeTraversal {
    /**
     * 递归先序遍历
     *
     * @param root
     */
    private static void preOrderRec(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val);
        preOrderRec(root.left);
        preOrderRec(root.right);
    }

    /**
     * 递归中序遍历
     *
     * @param root
     */
    private static void inOrderRec(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRec(root.left);
        System.out.print(root.val);
        inOrderRec(root.right);
    }

    /**
     * 递归后序遍历
     *
     * @param root
     */
    private static void postOrderRec(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrderRec(root.left);
        postOrderRec(root.right);
        System.out.print(root.val);
    }

    /**
     * @param root 利用栈实现循环先序遍历二叉树
     *             这种实现类似于图的深度优先遍历（DFS）
     *             维护一个栈，将根节点入栈，然后只要栈不为空，出栈并访问，接着依次将访问节点的右节点、左节点入栈。
     *             这种方式应该是对先序遍历的一种特殊实现（看上去简单明了），但是不具备很好的扩展性，在中序和后序方式中不适用
     * 因为先序遍历是 根左右，先左后右，又因为是借助栈结构，所以入栈要先右后左
     */
    private static void preOrderStack_1(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            System.out.print(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);

            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
    }


    public static void main(String[] args) {
        /**
         *              1
         *            /   \
         *           2     3
         *          / \   / \
         *         4   5 6   7
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode((4));
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
//    System.out.print("preOrderRec:");
//    preOrderRec(root);
        System.out.print("\ninOrderRec:");
        inOrderRec(root);
        System.out.print("\npostOrderRec:");
        postOrderRec(root);

//    System.out.print("preOrderStack_1:");
//    preOrderStack_1(root);
    }
}
